package _09_heap;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringJoiner;

/**
 * @author: mornd
 * @dateTime: 2023/6/10 - 22:10
 * leetcode 题：求出数据流的中位数
 */
public class MedianFinder {
    IntMaxHeap maxHeap = new IntMaxHeap(5);
    IntMinHeap minHeap = new IntMinHeap(5);

    void addNum(int num) {
        // 保证两个顶堆的元素值相差不会太大
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    double findMedian() {
        if(maxHeap.size == minHeap.size) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // 为什么返回右边，因为两个推大小相等时，是插入在右侧
            return minHeap.peek();
        }
    }

    @Override
    public String toString() {
        // 将大顶堆倒过来输出，保证大顶堆的堆顶在右侧
        var joiner = new StringJoiner(", ","[","]");
        for (int i = maxHeap.size - 1; i >= 0; i--) {
            joiner.add(String.valueOf(maxHeap.data[i]));
        }

        return """
                大顶堆>\t\t<小顶堆
                """ +
                joiner + " - " + minHeap;
    }
}
